package com.sxu.greedy.day4;

import java.util.Arrays;

/**
 * 无重叠区间
 */
public class Test22 {
    public int eraseOverlapIntervals(int[][] intervals) {
        // 左端点排序
        Arrays.sort(intervals, (v1, v2)->{
            return v1[0]-v2[0];
        });

        // 移除区间
        int ret = 0;
        int right = intervals[0][1];
        for(int i = 1; i < intervals.length; i++) {
            int a = intervals[i][0];
            int b = intervals[i][1];
            // 有重叠
            if(a<right) {
                ret++;
                // 贪心：删除右端点较大的区间
                right = Math.min(right, b);
            } else { // 没有重叠区间
                right = b;
            }
        }
        return ret;
    }
}
